This invention relates to a pattern matching device for carrying out pattern matching between two information compressed patterns by resorting to a DP (dynamic programming) technique on calculating a similarity or likelihood measure or degree between the patterns. Each of the patterns is generally an approximation of an original pattern represented by a sequence of feature vectors and is represented by a sequence of extracted vectors positioned with variable intervals or spacings along a time axis. The extracted vectors correspond to those representative or typical ones of the feature vectors for an original pattern which are arranged at such intervals to characterize the original pattern. In other words, the extracted vectors are feature vectors representative of each information compressed pattern.
Each original pattern may be given by a spoken word or a plurality of continuously spoken words. Alternatively, the pattern may be a figure or diagram which, in turn, may be type-printed characters or hand-printed letters. The pattern matching device serves as a main structural unit of a pattern recognition system as disclosed in U.S. Pat. No. 3,816,722 issued to Hiroaki Sakoe, one of the present applicants, et al, assignors to Nippon Electric Co., Ltd., the instant assignee. The pattern matching device is useful also in a continuous speech recognition system as revealed in U.S. Pat. No. 4,059,725 issued to Hiroaki Sakoe, one of the instant applicants, and assigned to the present assignee.
The DP technique or algorithm as called in the art, is resorted to in a majority of pattern matching devices which are in actual use. In preparation for the DP technique, the original patterns are represented by a first and a second sequence of feature vectors, respectively. Each sequence consists of a certain number of feature vectors depending on the pattern represented by the sequence under consideration. An intervector similarity measure is calculated between each feature vector of the first sequence and each feature vector of the second sequence. According to a DP technique, iterative calculation is carried out on a recurrence formula for use in defining a recurrence value by an extremum of several sums which are equal to a prescribed number of previously calculated recurrence values plus at least one intervector similarity measure, respectively. The extremum is a minimum and a maximum when the intervector similarity measure is given, for example, as a distance measure and a correlation measure between the two feature vectors, respectively. The recurrence formula eventually gives an interpattern similarity measure representative of whether the two original patterns are similar or dissimilar to each other. Depending on the circumstances, the intervector similarity measure may be called an elementary or primitive similarity measure. The interpattern similarity measure may be named an overall or eventual similarity measure.
For a pattern recognition system, a plurality of reference patterns are preliminarily registered in a pattern memory as reference feature vector sequences. An unknown pattern to be recognized, is supplied to a pattern buffer as an input feature vector sequence. The unknown pattern is subjected to the pattern matching operation successively with the reference patterns. The unknown pattern is recognized to be one of the reference patterns that provides an extremum interpattern similarity measure relative to the unknown pattern.
As will later be discussed more in detail with reference to a few of about fifteen figures of the accompanying drawing, each reference feature vector sequence consists of a considerable number of feature vectors. The number is called a reference pattern duration or length. A conventional pattern matching device must therefore comprise a pattern memory of an appreciably large memory capacity. A longer time is necessary on carrying out the pattern matching operation with each reference pattern when an input pattern is either long or covers a wide area to have, in either case, a longer input pattern duration or length. The device has therefore been bulky and expensive.
To speak of speech patterns by way of example, a variation in adjacent feature vectors is little at stationary part, such as in a vowel, and considerable at a transient part, such as at a transition from a vowel to a consonant. In other words, a feature vector sequence representative of a speech pattern, usually includes an appreciable number of redundant feature vectors which carry redundant information and are interspersed in a smaller number of representative feature vectors characterizing the speech pattern. It has therefore been proposed to substitute an information compressed pattern for an original pattern. The information compressed pattern is represented by a sequence of "extracted" vectors extracted directly from the original pattern at a plurality of those "extracting" instants or points, respectively, which are placed with variable intervals of time along a time axis, namely, positioned at discrete instants. The information compressed pattern is therefore represented by a combination of the extracted vector sequence and a timing or point sequence composed of the instants. The extracted vectors correspond to the respective characteristic feature vectors. Such an information compression technique is described in, for example, an article contributed by Theodosios Pavlidis to IEEE Transactions on Computers, Volume C-22, No. 7 (July 1973), pages 689-697, under the title of "Waveform Segmentation through Functional Approximation."
It may appear at a first sight that the memory capacity and the time of calculation will be reduced by applying the DP technique to the information compression technique. The fact is, however, not.
Even if the DP technique were successfully applied to the information compression technique, a conventional pattern matching device comprises a work memory and a calculating circuit which must deal with signals having a multiplicity of bits particularly when an input extracted vector sequence is considerably long.
On the other hand, it has been known as described in an article which Fumitada Itakura contributed to IEEE Transactions on Acoustics, Speech, and Signal Processing, Volume ASSP-23, No. 1 (February 1975), pages 67-72, and is entitled "Minimum Precision Residual Principle Applied to Speech Recognition," that the speed of pattern recognition can be increased by rejecting or discontinuing the pattern matching operation in a pattern recognition system if the reference pattern being subjected to the pattern matching operation, gives a distance measure which is greater than a predetermined threshold,